\documentstyle[fullpage,twocolumn,a4]{article}
	\oddsidemargin	-0.3in
	\evensidemargin	-0.3in
	\topmargin	-0.25in
	\headheight	0pt
	\headsep	0pt
	\textwidth	6.85in
	\textheight	9.4in
	\columnsep	0.38in
	\tolerance	1000
%	\pagestyle{empty}

\author{
	Daniel R. Edelson\thanks{
	    Author's other affiliation: Computer and Information Science, 
	    University of California, Santa Cruz, CA 95064, USA, 
	    {\sl daniel@cse.ucsc.edu}
	}
    \\[0.4cm]
	INRIA Project SOR \\
	Rocquencourt, BP 105 \\
	78153 Le Chesnay Cedex \\
	France \\
	{\sl edelson@sor.inria.fr}
}

\title{Draft: Precompiling C++ for Garbage Collection}
\date{26 March 1992}
\input{psfig}
%\input{code}

% FOR SINGLESPACE
%\def\C++{\leavevmode\rm{\hbox{C\hskip -0.1ex\raise 0.5ex\hbox{\tiny ++}}}}
%\def\<{{\small $<$}}
%\def\>{{\small $>$}}
%\def\code{\small \sf}
%\def\*{{\small $\ast$}}

% For DOUBLESPACE
\def\C++{\leavevmode\rm{\hbox{C\hskip -0.1ex\raise 0.2ex\hbox{++}}}}
\def\<{{$<$}}
\def\>{{$>$}}
\def\code{\sf}
\def\*{$\ast$}

%\def\code{\small \sf \def\<{{\small $<$}}\def\>{{\small $>$}}}
\def\ta#1{\mbox{\code $<$#1$>$}}

\def\List{{\code List}}
\def\NULL{{\code NULL}}
\def\class{{\code class}}
\def\const{{\code const}}
\def\volatile{{\code volatile}}
\def\arrow{$\Rightarrow$~}

%\newenvironment{codefig}{\small\begin{verbatim}}{\end{verbatim}}

%\def\codefig#1{\small \begin{verbatim} #1 \end{verbatim} }

\def\figcomment#1{\begin{quotation}{\small #1}\end{quotation}}


\begin{document}
\maketitle
\insert\footins{
{\footnotesize
    \vspace{.1in}
    Copyright (C) 1992 by Daniel R. Edelson, for submission to 
    the 1992 {\em Intl.\ Workshop on Memory Management}.
    \vspace{.1in}
}
}

\begin{abstract}
Our research is concerned with compiler-independent, efficient and
convenient, garbage collection for \C++.
Most collectors proposed for \C++ have either been implemented
in a library, or in a compiler.
As an intermediate step between those two,
this paper proposes using precompilation techniques to augment 
a \C++ source program with code to allow type-accurate garbage collection. 
In this way, the garbage collector can be more
portable and distributable than a collector within a compiler, while
simultaneously more convenient (i.e., more practical) than a type-accurate
collector that is implemented entirely within a library.

The collector that is under development is based on precompiler-generated
{\em smart pointers} as a replacement for raw pointers in the \C++
program. 
The precompiler emits the smart pointer definitions, and the
user is required to utilize them in place of raw pointers.
These smart pointers supply functionality that allows the
collector to locate all of the roots in the program. 
The precompiler also generates code that allows the collector to 
locate internal pointers within objects. 
This paper describes the architecture of the system,
whose first implementation as a simple mark-and-sweep collector
is underway. The paper also describes how the collector may eventually
be extended with generations.
\bigskip

\begin{center}
{\bf Keywords\vspace{-.5em}\vspace{0pt}}
\end{center}

\smallskip

\C++, garbage collection, compilers, precompilers, smart pointers, 
mark-and-sweep, memory management
\end{abstract}

\section{Introduction}

\C++ is nearly alone among modern object-oriented programming
languages in not providing garbage collection. The lack of GC
decreases productivity and increases memory management errors. This
situation persists principally because the common ways of implementing
GC are deemed inappropriate for \C++. In particular, tagged pointers
are unacceptable because of the impact they have on the efficiency of 
integer arithmetic, and because the cost is not localized.

In spite of the difficulty, an enormous amount of work has been and
continues to be done in attempting to provide garbage collection in
\C++. The proposals span the entire spectrum of techniques including
(not exhaustively):
\hyphenation{gener-a-tional}
\begin{itemize}
  \item concurrent atomic garbage collection implemented in
        the cfront \C++ compiler \cite{detlefs90},
  \item library-based object-management including reference
        counting and mark-and-sweep \cite{oath},
  \item library-based mostly copying gen\-er\-a\-tional garbage collection
        from ambiguous roots \cite{bartlett:mostly},
  \item library-based reference counting through 
        {\em smart pointers}\footnote{Smart pointers
        \cite{St91,St:evolution,edelson:usenix92} are discussed later
        in this paper.} \cite{maeder92},
  \item library-based mark-and-sweep garbage collection using
        smart-pointers \cite{edelson:popl92}
  \item compiler-based garbage collection using smart pointers
        \cite{ginter:91},
  \item library-based mark-and-sweep or copying collection using
        macros \cite{ferreira:91}, and 
  \item library-based conservative generational garbage collection
        \cite{uncoop:BW88,demers:conservative}.
\end{itemize}
The vast number of proposals, without the widespread acceptance of any
one, reflects how hard the problem is.

The goal of our research is to make type-accurate garbage collection 
available to the \C++ community. This ideal imposes strong 
restrictions on the collector. Given the speed with which \C++ compiler 
technology and the \C++ language definition are advancing, any particular 
version of any compiler quickly becomes obsolete. In order to be 
carried along with the evolution of the state-of-the-art, and to be usable by 
anybody regardless of what compiler they choose, the collector must
not be implemented in the compiler.

In the past, we have proposed implementing GC strictly 
in application-code. It would be something like ``GC implemented
in a library.'' The problem with this approach was that it required
too much effort from the user. They had to first customize/instantiate
the library (a substantial piece of work), and then follow its rules.
Overall, this was a tedious and error prone process.

To solve our goal of compiler-independence, while keeping the associated
complexity to the user to a minimum, we are now proposing 
{\em precompiling\/}
\C++ programs to augment them for garbage collection. In essence, the
precompiler performs the necessary customization on the \C++ program
every time it gets compiled. The user still needs to cooperate with the
collector, but the number of things to remember (and thus the 
likelihood of errors) is greatly reduced.

In this paper we discuss our collector architecture and related 
techniques for supplying garbage collection at the \C++ source code level. 
Then, we describe the transformations that augment a \C++
program with the necessary code for it to utilize garbage collection.
The remainder of the paper is organized as follows:  
Section \ref{related} discusses related work in 
garbage collection and memory management for \C++.
Section \ref{overview} provides an overview of the major techniques 
that we utilize to implement garbage collection.
Section \ref{xform} describes the transformations that the proposed 
precompiler carrys-out to augmented a program for GC. 
Finally, section \ref{conclusion} concludes the paper. 

\section{Related Work}					\label{related}

There is a significant body of related work, in the general field of
GC, in \C++ software tools, and specifically in collectors for \C++.

\subsection{Conservative GC}

Conservative garbage collection is a technique in which the collector
does not have access to type information so it assumes that anything
that might be a pointer actually is a pointer \cite{boehm91,uncoop:BW88}.
For example, upon examining a quantity that the program interprets 
as an integer (in a register, perhaps), but whose value 
is such that it also could be a pointer, the collector would assume 
the value to be a pointer. This is a useful technique for 
accomplishing garbage collection in programming
languages that don't use tagged pointers, 
and in the absence of compiler support.

Boehm, Demers, et al.\ describe conservative, generational, parallel 
mark-and-sweep garbage collection 
\cite{boehm91,uncoop:BW88,demers:conservative} 
for languages such as C.
Russo has adapted these techniques for use in
an object-oriented operating system 
written in \C++ \cite{russo91,russo91:pos}. 
Since they are fully conservative,
during a collection these collectors must examine every word of the stack, 
of global data, and of every marked object.
In addition, Boehm discusses compiler changes to preclude optimizations
that would cause a conservative garbage collector to reclaim data that 
is actually accessible \cite{boehm:position:gc91}.

Conservative collectors sometimes retain more gar\-bage than
type-accurate collectors because conservative collectors interpret 
non-pointer data as pointers. Often, the amount of retained 
garbage is small, and conservative collection succeeds quite well. 
Other times, conservative techniques are not satisfactory.
For example, Wentworth has found that conservative garbage collection 
performs poorly in densely populated 
address spaces \cite{pitfalls:wentworth90,wentworth:phd}. 
Russo, in using a conservative collector to reclaim
dynamic storage used by an object-oriented operating system, has also 
found that inconveniently large amounts of 
garbage escape collection \cite{russo91}. 
Lastly, we have tested conservative garbage collection with a CAD software 
tool called ITEM \cite{minimize-caltech89,edelson:m-s,edelson:popl92}.
This application creates large data structures that are strongly
connected when they become garbage. A single false pointer into the
data structure keeps the entire mass of data from being reclaimed.
Thus, our brief efforts with conservative collection in this
application proved unsuccessful. 

As these examples illustrate, conservative collection is a very useful
technique, but it is not a panacea. Since it has its 
bad cases, it is worthwhile to investigate type-accurate garbage 
collection. 

\subsection{Partially Conservative}

Bartlett has written the {\em Mostly Copying Collector},
a generational garbage collector for Scheme and \C++ that uses both 
conservative and copying techniques \cite{bartlett:mostly,compact:Ba88}.
This collector divides the heap into logical pages, each of which
has a {\em space-identifier}. During a collection an object can be
promoted from from-space to to-space in one of two ways:
it can be physically copied to a to-space page, or the space-identifier
of its present page can be advanced. 

Bartlett's collector conservatively scans the stack and global data 
seeking pointers.
Any word the collector interprets as a pointer (a root) may in fact 
be either a pointer or some other quantity.
Objects referenced by such roots must not be moved because,
as the roots are not definitely known to be pointers,
the roots can not be modified.
Such objects are promoted by having the space identifiers
of their pages advanced. Then, the root-referenced objects
are (type-accurately) scanned with the help of information provided 
by the application programmer; the objects they reference are compactly 
copied to the new space. 
This collector works with non-polymorphic \C++ data structures,
and requires that the programmer make a few declarations to enable
the collector to locate the internal pointers within collected objects.

Detlefs generalizes Bartlett's collector in two ways \cite{detlefs90}. 
Bartlett's collector contains two restrictions:
\begin{enumerate}
\item	Internal pointers must be located at the
	beginning of objects, and
\item	heap-allocated objects may not contain ``unsure'' 
	pointers.\footnote{An unsure pointer is a quantity that is statically 
typed to be either a pointer or a non-pointer. For example, in 
{``\sf union \{ int i; node \* p; \}x;\/''}
{\sf x} is an unsure pointer.}
\end{enumerate}
Detlefs' relaxes these by maintaining type-specific map information
in a header in front of every object. During a collection the 
collector interprets the map information to locate internal pointers.
The header can represent information about both sure pointers and
unsure pointers. The collector treats sure pointers accurately and
unsure pointers conservatively.
Detlefs' collector is concurrent and is implemented
in the {\em cfront\/} \C++ compiler.

\subsection{Type-Accurate Techniques}

Kennedy describes a \C++ type hierarchy called OATH that uses 
garbage collection \cite{oath}. 
Its collector algorithm uses a combination of reference counting 
and mark-and-sweep. In OATH, objects are accessed exclusively 
through references called {\em accessors}. An accessor implements 
reference counting on its referent. 
Thus, the first reclamation algorithm available for
OATH objects is reference counting. In addition, the reference counts
are used to implement a three-phase mark-and-sweep algorithm
that can collect cyclic data structures. The three-phase algorithm
proceeds as follows.
First, OATH scans the objects to eliminate from the 
reference counts all references between objects. 
After that, all objects with non-zero reference counts
are root-referenced. The root-referenced objects serve as the roots
for a standard mark-and-sweep collection, during which the reference
counts are restored.

In OATH, a method is invoked on an object by invoking
an identically-named method on an accessor to the object. 
The accessor's method forwards the call through a private pointer
to the object.
This requires that an accessor implement all the same methods
as the object that it references. Kennedy implements this using 
preprocessor macros so that the methods only need to be defined once.
The macros cause both the OATH objects, and their accessors, to be
defined with the given list of methods. While not overly verbose,
the programming style that this utilizes is quite different from the 
standard \C++ style. Additionally, current compiler technology renders
long macros, such as those required for OATH, quite difficult to debug.
A precompiler would have substantial benefits over a preprocessor
for a system like OATH.

Goldberg describes tag-free garbage collection for
polymorphic statically-typed languages using compile-time
information \cite{goldberg91}, building on work by Appel \cite{appel89}.
Goldberg's compiler emits functions that know how to locate the pointers
in all possible (necessary) activation records of the program.
For example, if some function $\cal{F}$ contains two pointers as local 
variables, then another function would be emitted to mark from those pointers
during a collection. The emitted function would be called once for every
active invocation of $\cal{F}$, on the stack, upon a collection, to
trace or copy the sub-datastructure reachable from each pointer.
Upon a collection, the collector follows the chain of return 
addresses up the run-time stack. 
As each stack frame is visited, the correct garbage collection 
function is invoked. A function may have more than one garbage collection
routine because different variables are live at different points
in the function. Clearly, this collector is very tightly coupled to 
the compiler.

Yasugi and Yonezawa discuss user-level garbage
collection for the concurrent object-oriented programming language
ABCL/1 \cite{yasugi91:position}. Their programming language is based
on active objects, thus, the garbage collection requirements for this
language are basically the same as for garbage collection 
of Actors \cite{dickman:gc92,kafura:actors:gc}.
Their position paper describes a process very similar to the one proposed
in this paper, namely, translating a source program into another
source program that is augmented for GC. 
The programming paradigms for \C++ 
and ABCL/1 \cite{ansiC++,yonezawa90} are quite different;
each introduces its own problems that the collector needs to solve.

Ferreira discusses a \C++ library that provides garbage collection
for \C++ programs \cite{ferreira:91}. The library supplies both 
incremental mark-and-sweep and generational copy collection, and supports
pointers to the interiors of objects. The programmer renders the
program suitable for garbage collection be placing macro definitions
at various places in the program. For example, every constructor must
invoke a macro to register the object, and every destructor must invoke
the complementary a macro to un-register the object. 
Another macro must be invoked in the class definition to add GC members to
the class, based on the number of base classes of the class.
To implement the remembered set for generations (cf \ref{generations}),
the collector requires a macro invocation on every assignment to an 
internal pointer.
Similarly to the collector we describe in \cite{edelson:popl92}, 
this collector requires that the programmer supply 
a function to locate internal pointers. Ferreira's
collector can also scan objects conservatively in order to obviate
the need for programmer-coding of this function.

Maeder describes a \C++ library for symbolic computation systems based 
on smart pointers and reference counting \cite{maeder92}. The library 
contains class hierarchies for {\em expressions}, {\em strings}, {\em symbols}, 
and other objects that are called {\em normal}. To improve the efficiency
of assignment of reference counted pointers, Maeder uses the
address of a discrete object as a replacement for the \NULL\ pointer.
The smart pointers support debugging by allowing the programmer
to detect dangling references: rather than being deleted, an object
is marked {\em deleted}, and subsequent accesses to the object cause
an error to be reported. Other functionality allows the programmer
to detect memory leaks, by reporting objects that are still alive when
the program terminates.

\section{Overview} \label{overview}

The two hard problems that a garbage collector must solve are: 1)
finding all the pointers that reference dynamically allocated objects, 
and 2), locating pointers within objects.
Pointers of the first kind are called {\em roots}; pointers of the second
kind are called {\em internal pointers}. 

Our collector locates the roots by requiring that 
they be indirected through the {\em root table}. 
The internal pointers are located using
structure tags that are associated with all dynamically allocated 
objects, and that index information about the type of
the object to determine the offsets of their internal pointers.
Some pointers are not handled in either of these two ways;
they will be discussed later.

\subsection{Indirect Root Tables}

This collector is based on root indirection.  Every root that the
application manipulates is indirect through the {\em root table}.
The root table consists of one or more arrays of cells. 
A cell that is in use, and
therefore that contains a direct pointer, is called {\em active}; a
cell that is free is called {\em inactive}.  The inactive cells are
linked into a free list.  Whenever a cell is required, one is taken from
this list.  When no free cell is available, a new cell array is
allocated.  The root table initially consists of a single cell array;
but more may be added over a program's lifetime.  Figure
\ref{indir-tab} illustrates a table consisting of a single cell array.
In figure \ref{indir-list} the root table has been extended with
another array.

\begin{figure}[bt]
\centerline{\psfig{file=figs/direct.ps,width=3.0in}}
\caption{Root indirection}
\figcomment{
    The mutator's roots are indirect through the root table.
    The root table contains {\em active\/} cells and free cells.
    The free cells are linked into a free list.
}

\bigskip
\hrule
\label{indir-tab}
\end{figure}

\begin{figure}[bt]
\centerline{\psfig{file=figs/list.ps,width=3.0in}}
\caption{The list of root tables}
\label{indir-list}
\figcomment{
    The root table consists of cell arrays that are
    linked into a list.  The first word of each array contains its link.
}

\bigskip
\hrule
\end{figure}

When allocating a new cell, it is necessary to be sure that one is
available.
Normally, this would require a test and a conditional branch. Upon
obtaining the pointer to the next free cell, the root table management
code would check to be sure that the pointer is not \NULL. However, the
first thing that is ever done with the new cell is to read it's 
value to obtain the next link in the free list of cells. We can use
that read operation to eliminate the test and conditional branch.

There is always one cell array that was the last to be allocated. This
array is special in that its inactive cells are {\em
sequentially\/} linked into a free list. This must be true, because
when the array is allocated, all of its cells are free, and they are
all linked into a free list. We {\em read protect\/} the last page of
this array \cite{appel:vm}. During program execution, when we attempt
to load the link stored in the first cell on the read protected page,
the program receives and handles a signal. That signal tells the
system to allocate and link in a new cell array. 
A new diagram of a cell array is presented in
figure \ref{protected-tab}. 
The shaded area illustrates the read-protected region.

\begin{figure}[tbh]
\centerline{\psfig{file=figs/protected.ps,width=3.25in}}
\caption{A cell array's protected page}
\label{protected-tab}
\figcomment{
    The most recently allocated cell array has its last page read
    protected. When the protection violation occurs, a new array is
    allocated and linked to the others.
}

\bigskip
\hrule
\end{figure}

\subsection{Smart Pointers}

We have indicated that pointers manipulated by the programmer 
must be indirect through the root table, but we have not indicated
how this is accomplished. We require that the programmer use
{\em smart pointers\/} \cite{St91,St:evolution,edelson:usenix92}
in place of pointers. Smart pointers are user-defined \C++ class 
objects that behave like pointers. The smart pointers use operator
overloading so that the standard indirection operators, {\code \*}
and {\code -\>}, can be used to transparently access objects and members 
through the smart pointers.

There is a discussion of the best way to organize smart pointers
for a polymorphic \C++ class hierarchy in \cite{edelson:usenix92}.
The basic goal is to support both polymorphism, and smart pointers
to \const\ objects. To accomplish this, we use two smart pointer classes
for every user class. One of the smart pointer classes
substitutes for pointers to mutable objects; the other replaces pointers
to \const\ objects. These two classes are related in that one is a
derived class of the other. Specifically, the smart pointer class for
mutable objects derives from the smart pointer class for \const\ objects.
This supplies an implicit type conversion, in the desired direction,
between the two classes.

A similar technique could be used to support implicit pointer type 
conversions for pointers to base class objects and pointers to derived 
class objects \cite{oath}. However, this fails in the
presense of multiple inheritance and permits an erroneous type 
conversion \cite{edelson:usenix92}. Therefore, we support smart pointers
in a class hierarchy through user-defined type conversions. Figure
\ref{smarthier} shows a hierarchy of user-classes, along with the 
corresponding smart-pointer organization.

The next question is how to insert the smart pointer class
definitions into the program.
\C++ contains a mechanism for implementing {\em parameterized types\/}, 
called {\code template}s, 
that seems like the perfect technique. However, generation from templates
does not give the smart pointer classes the implicit type conversions
that they must have to behave like normal pointers. Thus, templates alone 
are not sufficient. One way to define them would be through hand
coding, abbreviated with preprocessor macros.
Grossman \cite{grossman92}, for example, uses smart pointers
similar to ours for transparent access to objects on 
disk or across a network. In his system, the 
smart pointers are defined through hand-coding, 
but inheritance is used to eliminate some redundant code. 
We, too, suggested hand coding with macros in \cite{edelson91}. 
However, this is inconvenient and error-prone.  
This paper proposes that
a \C++ precompiler generate the smart pointer classes.

\begin{figure*}[bth]
%{\singlespace
%\raisebox{-.6in} [3.2in][0in]
	{\centerline{\psfig{file=figs/smarthier.ps,height=3.5in}}}
\caption{The smart pointer organization for the indicated user classes.}
\label{smarthier}
%}
\bigskip
\hrule
\end{figure*}

\subsubsection{Using Smart Pointers}

As in \cite{edelson:popl92}, this collector requires that the 
programmer utilize smart pointer objects in place of raw pointers.
A precompiler could detect the declaration and
use of raw pointers and substitute smart pointers, but 
we are initially trying to achieve somewhat more modest goals.
Thus, we continue to require that the programmer manipulate
objects of type ``{\code R\_{\em T}}\/'' rather than raw pointers of
type {\code {\em T}\*}.

\subsection{Internal Pointers}

The collector described in \cite{edelson:popl92} requires
users to supply a hand-coded {\code mark()} function
for each type of collected object.
This function locates the internal pointers for the collector.
The mark functions are selected through static function
overloading.\footnote{Combined with {\code virtual} functions when 
necessary.}
This is possible because the collector uses multiple
root tables, in particular, the collector used one root table per 
static type of smart pointer. 

The advantage of this scheme is that absolutely no dynamic type information
is required by the collector for non-polymorphic data structures.
In particular, there are no structure tags. 
The main disadvantages of this approach are twofold. Firstly, hand coding
is error prone. If a user changes a class definition, they may also
need to change the {\code mark()} function;
failure to do so can lead to obscure gc errors. 
Secondly, the use of many root tables leads to fragmentation. 
This wastes memory and decreases efficiency.

In order not to fragment memory among many root tables, this implementation
uses only a one root table. 
Some dynamic mechanism is thus required for identifying 
internal pointers: dynamic objects are given structure tags.
Standard \C++ features are used to assign an 
unique integer to every garbage collected class. When an object is
allocated, its tag is passed in to the memory allocator through the
overloaded {\code new} operator. The tag is stored in the allocator
header associated with the object.

Separately, the precompiler locates the offsets of the internal pointers
in every collected class, and creates a vector of those offsets.
Any unsure pointer \cite{detlefs90} is treated conservatively, as
in Detlefs' collector. Then, the vector of offsets is registered
in the memory allocator with the type's tag. This combination of structure
tags and internal pointer offsets allows the collector to traverse the
data structure.

\subsection{Garbage Collection} \label{gc}

The collector is currently a stop-the-world mark-and-sweep collector.
Collection can be triggered by any one of a number of events.
The user can trigger a collection if it is known that a lot of 
garbage has been produced. Alternatively, the memory allocator
can initiate garbage collection because an allocation limit has
been reached. 

In order to collect garbage, the collector examines every cell in the
root table. A cell that is free contains a free-list pointer to another 
cell. Thus, any cell that points into some cell array of the root table 
does not contain a direct pointer. By contrast, cells that do not point 
into the root table contain direct pointers. The mark algorithm is invoked 
on those cells to set the mark bits associated with the reachable data 
structure.

The traversal algorithm for marking uses explicit stacking and iteration.
Every time an object is visited, its mark bit is tested and set.
If the object was previously unmarked, the structure tag in the object's
allocation header is used to obtain information about internal pointers.
Then, the internal pointers are pushed onto the stack and the algorithm
continues with the next pointer in the stack.

\section{Precompilation} \label{xform}

The precompiler preprocesses a file, parses it, and then performs
the following transformations:

\begin{itemize}
\item	For every class, the precompiler emits smart pointer definitions
	to replace raw pointers for referring to objects of that class.
	The smart pointer definitions are prepended to the file.

\item	Code is inserted to generate a structure tag for every class. 
	The {\code new} operator is overloaded for the class so that, 
	every time an object is allocated, the structure tag for the
	object's type is passed into the allocator where the tag is 
	stored in the allocation header. The class must use this operator 
	{\code new}; the user cannot supply another one.

\item	For every class, the internal pointer offset information is 
	generated. Specifically, the offsets of internal pointers are
	compiled into a vector and associated with the type's structure
	tag. Thus, given an object and the corresponding structure tag, 
	the collector can identify the pointer members of the object. 
	These pointer members include not just normal members, 
	but also members of nested types.
\end{itemize}

In a future step, the programmer could actually program
with raw pointers. The precompiler would recode the application
to use smart pointers instead of raw pointers. But this is not yet
under consideration as the ramifications of this proposal are quite 
substantial.

\subsection{Unsure Pointers}

An {\em unsure} pointer is a datum that might be a pointer or might
not \cite{detlefs90}. For example, in conservative collection,
every properly aligned word of program data is an unsure pointer because 
the collector does not have access to type information, 
and thus cannot know what actually is a pointer.
This collector uses much more type information than a conservative
collector, but can not\footnote{and should not, e.g., {\code union}s}
totally eliminate unsure pointers.
To deal with them, and also to be efficient, this collector uses
conservative techniques in two ways.

One place where this collector is conservative is on pointers
that are unsure at the \C++ source code level. For example, if an
object contains a member that is a {\code union} of a pointer and
a non-pointer, the precompiler would treat that member as a pointer.
The second place where the collector is conservative is on {\code this} 
pointers.

\subsection{{\tt this} pointers}

In C++, whenever a method (member function) is invoked on
an object, a pointer to the object is passed to the method on the
stack.  This pointer is called the {\code this} pointer.  Through the
{\code this} pointer the method can access the object's instance data.

These pointers are potentially roots. 
However, {\code this} pointers are very common and we don't want to
negatively impact their efficiency. Furthermore, they are managed
by the compiler, from which this collector is independent. Thus,
we do not impose any special behavior, semantics, or indirection on 
{\code this} pointers.
The solution we propose is to coarsely decode the stack, treating every
word that might be a {\code this} pointer conservatively.

In every activation record on the call stack, 
if the call is to a member function, 
then the first function parameter is a {\code this} pointer.
That parameter is always in a known place in a register or in memory.
We can decode the stack just sufficiently to examine the first 
parameter to every function. This parameter will be 
treated conservatively on the assumption that it may be a {\code this} 
pointer.

%\subsection{Memory Allocator Functionality}
%
%As is clear from the description, this collector can not
%always differentiate between an integer and a pointer. For instance,
%it treats unsure pointers and {\code this} pointers conservatively.
%In addition, it is absolutely imperative that the collector
%work properly in the presense of multiple inheritance. 
%In \C++, multiple inheritance causes many interior pointers, i.e., 
%pointers to the interiors of objects, to be created. For these two reasons,
%the collector must be able to determine if an arbitrary value points
%to an object. Additionally, the allocator must be able to detect an
%interior pointer, and to convert it to a pointer to the beginning
%of the object. This must be done in order to locate the object's 
%structure tag and internal pointers.
%
%This is a difficult task for a memory allocator. 
%To accomplish this in hard real-time systems, 
%Schmidt and Nilsen propose using custom 
%hardware \cite{schmidt:nilsen:hardware,nilsen91}.
%More mundanely, Boehm's and Ferreira's systems 
%accomplish this in software \cite{boehm91,ferreira:91}.
%The memory allocator that we are developing for this, like Boehm's
%and Ferreira's, accomplishes this in software.
%This allows the collector to fully support both
%multiple inheritance and interior pointers.
%By contrast, the allocator that we supplied in \cite{edelson:popl92}
%lacked this functionality.

\subsection{Generations}			\label{generations}

In generational garbage collection, the objects are segregated into
{\em transient\/} objects and non-transient objects, where the transient
objects are expected to become garbage quickly
\cite{soar86,tenure:UJ88,moon:ephemeral_gc,collector:LH83,demers:conservative,wilson:issues}. 
The collector concentrates its effort on the transient objects,
and does not spend time collecting stable objects that have probably not
become garbage.
The following observation is exploited to
determine which objects are transient and which are not: {\em young
objects tend to die young, and old objects tend to persist\/} \cite{soar86}.
Thus, generational collectors concentrate their effort on the young
objects and collect older objects much less frequently.

The difficult problem in implementing the {\em remembered set}. 
The remembered set is those references from old objects to young
objects, called {\em back-pointers}.
This set is needed in order to collect the young objects, 
since, when collecting the young objects, the roots are all of the
normal pointers (on the stack, in global data, and in registers), and
also the pointers contained in old objects that reference young objects.
Maintaining the remembered set is that main source of overhead for
generational collectors.

Demers et al.\ \cite{demers:conservative} implement the remembered set
in a conservative collector as follows.
The remembered set is those pages of old space that are thought to
contain pointers to the young space.
The remembered set is initially empty, and all the pages of the old-space
are write-protected using the operating system interface
to the virtual memory hardware.
Then, every time the mutator writes to a protected old-space page, 
the program receives an exception that is handled by the collector.
The collector unprotects, and adds to the remembered set, the page on 
which the fault occurs. After this, the mutator can write to the
page freely. 
This allows the collector to identify a superset of 
the pages that contain back-pointers.
During a collection, the 
collector conservatively scans all of the pages that are in the 
remembered set. Any page that does not contain at least one pointer to
a young object is deleted from the remembered set and re-write-protected.

This technique can be used in our collector.
It is our intention to implement it as soon as work on the precompiler
and basic memory allocator is sufficiently advanced.

\subsection{Status}

The design and development of this system are both underway.
The smart pointers work, as does most of the code to perform
a garbage collection. The precompiler has been prototyped
using an existing \C++ compiler as the starting point. 
The modified C++ compiler parses the user's \C++ code and emits
smart pointers and other declarations. 
The precompiler does not yet
reintegrate the emitted code back into 
the original source program.
The simple non-generational mark-and-sweep collection algorithm, 
using explicit stacking, has been implemented. 
The memory allocator and the conservative scan for {\code this} pointers
are being implemented.

\section{Conclusions}					\label{conclusion}

\C++ is a very well designed language considering its goals, however,
the complexity of its semantics is daunting. Adding to that complexity
by requiring manual storage reclamation makes programming in \C++
difficult and error-prone. A widely available garbage collector
would be of great benefit to the community.

Many garbage collectors have been proposed for C++ but none has yet
gained widespread acceptance. Some are tightly coupled to the compiler;
such collectors must be supported by a major \C++ compiler vendor, 
otherwise the compiler that implements the collector will quickly
become obsolete. Other collectors are loosly coupled to the compiler.
These collectors sometimes require considerable effort and/or 
impose restrictions for programmers. As an intermediate step between these
two extremes, this paper proposes precompiling \C++ programs for
garbage collection. For type-accurate garbage collection, this is 
more convenient for the programmer than a pure library-based approach.
Simultaneously, this is very portable and does not require that customers
utilize any specific compiler.

The collector that we describe is under implementation as an (initially)
non-generational mark-and-sweep collector. After it is running, we will
immediately add generations, and eventually, concurrency. This has the
possibility of providing efficient convenient garbage collection to
a large part of the \C++ programming community.

\section*{Acknowledgements}

I would like to thank Peter Dickman for his helpful comments after
reading a draft of this paper. I would also like to thank Marc Shapiro
for supporting this research.

\bibliographystyle{alpha}
\bibliography{abbrev,oopsla90,langs,thesis,garbage,soar,proceed}
\end{document}
